﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0165_FindRepeatedDnaSequences : IAlgorithm
    {
        // 187. 重复的DNA序列

        // DNA序列 由一系列核苷酸组成，缩写为 'A', 'C', 'G' 和 'T'.。
        //  例如，"ACGAATTCCG" 是一个 DNA序列 。
        // 在研究 DNA 时，识别 DNA 中的重复序列非常有用。
        // 给定一个表示 DNA序列 的字符串 s ，返回所有在 DNA 分子中出现不止一次的 长度为 10 的序列(子字符串)。你可以按 任意顺序 返回答案。

        // 提示：
        //  0 <= s.length <= 10^5
        //  s[i]=='A'、'C'、'G' or 'T'

        public void Test()
        {
            var res = FindRepeatedDnaSequences("AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT");
            foreach (var item in res)
            {
                Console.Write(item + " ");
            }
        }

        // 算法
        //"AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
        public IList<string> FindRepeatedDnaSequences(string s)
        {
            var res = new List<string>();
            if (s.Length <= 10)
                return res;
            var map = new Dictionary<string, int>();
            for (int i = 10; i <= s.Length; i++)
            {
                var temp = s[(i - 10)..i];
                if (map.ContainsKey(temp))
                    if (!res.Contains(temp))
                        res.Add(temp);
                    else
                        continue;
                else
                    map.Add(temp, 1);
            }
            return res;
        }
    }
}
